package com.kznnc.data_structure.structure.queueStructure;

/**
 * @Description 双端队列  每一端都可以进行出队和入队
 * 双端队列 只提供了两端都可以进行出队和入队的操作  并不能强制的保证FIFO
 * FIFO是由使用者是自己保证的
 * @Author houchenkai
 * @Created Date: 2021/4/9 15:50
 * @ClassName
 */
public class ArrayDoubleQueue {

    private int portOne;

    private int portTwo;

    private Integer[] data;


    public ArrayDoubleQueue(int capacity) {
        this.data = new Integer[capacity];
    }


    // 双端队列
    // 1.双端队列什么时候队列满 portTwo -portOne == data.length
    // 2.队列什么时候为空 portTwo == portOne;
    // 3.数组作为存储的结构时,顺序存储结构 规定了存储数据的位置  当移除元素后,需要移动位置 才能保证队列不出现伪溢出
    //   移动元素位置就是为了防止伪溢出


    public void pushFirst(Integer num) {
        int size = portTwo - portOne;
        if (size >= data.length) {
            throw new RuntimeException("队列溢出");
        }

        if (portOne !=0){
            data[-- portOne] = num;
            return;
        }
        if (portTwo == data.length) {
            Integer[] newData = new Integer[data.length];
            int a = 0;
            for (int i = portOne; i < portTwo; i++) {
                newData[a++] = data[i];
            }
            data = newData;
            portOne = 0;
            portTwo = size;
        }

        for (int i = portTwo - 1; i >= 0; i--) {
            data[i + 1] = data[i];
        }
        data[0] = num;
        portTwo++;
    }

    public void pushLast(Integer num) {
        int size = portTwo - portOne;
        if (size >= data.length) {
            throw new RuntimeException("队列溢出");
        }
        // 此时为 伪溢出  进行移动
        if (portTwo == data.length) {
            Integer[] newData = new Integer[data.length];
            int a = 0;
            for (int i = portOne; i < portTwo; i++) {
                newData[a++] = data[i];
            }
            data = newData;
            portOne = 0;
            portTwo = size;
        }
        data[portTwo++] = num;
    }


    public Integer takeFirst() {
        int size = portTwo - portOne;
        if (size <= 0) {
            return null;
        }
        Integer first = data[portOne];
        data[portOne] = null;
        portOne++;
        return first;
    }

    public Integer takeLast() {
        int size = portTwo - portOne;
        if (size <= 0) {
            return null;
        }
        --portTwo;
        Integer result = data[portTwo];
        data[portTwo] = null;
        return result;
    }

    public void printerData() {
        for (Integer datum : data) {
            System.out.println(datum);
        }

    }

    public static int getAbsolute(int para) {
        // (para>>>31)  获取符号位
        // 先右移31位获取到符号位 负数符号位为1 左移后 10 等于 2   正数符号位为 0 左移后 00 还是 0
        //  1- 2= -1 (负数计算完)==>para 负负得正   1-0 = 1  para 正正得正
        return para * (1 - ((para >>> 31) << 1));
    }

    public static void main(String[] args) {

        ArrayDoubleQueue arrayDoubleQueue = new ArrayDoubleQueue(4);
        arrayDoubleQueue.pushFirst(1);
        arrayDoubleQueue.pushFirst(2);
        arrayDoubleQueue.pushFirst(3);
        arrayDoubleQueue.pushFirst(4);
        arrayDoubleQueue.printerData();
        System.out.println("-------------------------");
        arrayDoubleQueue.takeFirst();
        arrayDoubleQueue.takeFirst();
        arrayDoubleQueue.printerData();
        System.out.println("-------------------------");
        arrayDoubleQueue.pushFirst(0);
        arrayDoubleQueue.printerData();
        System.out.println("-------------------------");
        arrayDoubleQueue.pushLast(0);
        arrayDoubleQueue.printerData();

    }


}
